package leetcode;

import java.util.ArrayList;
import java.util.List;

public class TrianglePath {

	public static void main(String[] args) {

//		ArrayList<Integer> list = new ArrayList<Integer>();
//		ArrayList<ArrayList<Integer>> triangle = new ArrayList<ArrayList<Integer>>();
//		list.add(2);
//		triangle.add(list);
//		ArrayList<Integer> list1 = new ArrayList<Integer>();
//		list1.add(3);
//		list1.add(4);
//		triangle.add(list1);
//		ArrayList<Integer> list2 = new ArrayList<Integer>();
//		list2.add(6);
//		list2.add(5);
//		list2.add(7);
//		triangle.add(list2);
//		ArrayList<Integer> list3 = new ArrayList<Integer>();
//		list3.add(4);
//		list3.add(1);
//		list3.add(8);
//		list3.add(3);
//		triangle.add(list3);
//		TrianglePath path = new TrianglePath();
//		System.out.println(path.minimumTotal(triangle));
		
		List<Integer> list = new ArrayList<Integer>();
		List<List<Integer>> triangle = new ArrayList<List<Integer>>();
		list.add(-1);
		triangle.add(new ArrayList<>(list));
		list.clear();
		list.add(-2);
		list.add(-3);
		triangle.add(new ArrayList<>(list));
		list.clear();
		list.add(4);
		list.add(1);
		list.add(8);
		triangle.add(list);
		
		TrianglePath object = new TrianglePath();
		object.minimumTotal2(triangle);
	}

	public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
		if (triangle == null) {
			System.err.println("wrong input");
			return -1;
		}
		int rows = triangle.size();
		int columns = triangle.get(rows - 1).size();
		int[][] dp = new int[rows][columns];
//		for (int j = 0; j < columns; j++) {
//		}
		dp[0][0] = triangle.get(0).get(0); // dp[0] init
		for (int i = 1; i < rows; i++) {
			for (int j = 0; j < i + 1; j++) {
				if (j == 0) {
					dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j);
				}else if (j == i) {
					dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
				} else {
					dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1])
							+ triangle.get(i).get(j);
				}

			}
		}
		int minSum = Integer.MAX_VALUE;
//		for (int i = 0; i < dp.length; i++) {
//			for (int j = 0; j < columns; j++) {
//				System.out.print(" " + dp[i][j]);
//			}
//			System.out.println();
//		}
		for (int j = 0; j < columns; j++) {
//			System.out.println(" jieguo "+dp[rows - 1][j]);
			if (dp[rows - 1][j] < minSum) {
				minSum = dp[rows - 1][j];
			}
		}
//		System.out.println("min sum" + minSum);
		return minSum;
	}
	
	public int minimumTotal2(List<List<Integer>> triangle) {
        if(triangle == null){
            return 0;
        }
        int length = triangle.size();
        int[][] dp = new int[length][length];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < dp.length; i++) {
			dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
		}
        for (int i = 1; i < length; i++) {
			for (int j = 1; j < i; j++) {
				dp[i][j] = Math.min(dp[i - 1][j], dp[i -1][j - 1]) + 
						triangle.get(i).get(j);
			}
			dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
		}
		int res = Integer.MAX_VALUE;
		for(int i = 0; i < length; i++){
		    res = Math.min(res, dp[length - 1][i]);
		}
		
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				System.out.print(" " + dp[i][j]);
			}
			System.out.println();
		}
        return res;
    }
}
